package features.advance.nowcoder.recruitment;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 牛客网，模拟校招
 *
 *  魔法师牛牛
 * 难度：三星
 * 时间限制：C/C++ 1秒，其他语言2秒
 * 空间限制：C/C++ 256MB，其他语言512MB
 * 64bit IO Format: %lld
 * 知识点：思维、前缀和、排序
 * 题目描述
 * 牛牛拿到了一个长度为  的数组 , 作为一个魔法师，他可以每次选择一个 ，施展一次魔法使  加1或者减1。现在对于每一个  ，牛牛想知道将  中所有的数字变成  最少要施展几次魔法。
 *
 * 函数传入一个数组，你需要返回一个数组，假设数组为，则是将  中所有的数字变成  最少施展魔法的次数。
 *
 * 样例1
 * 输入
 * [3,1,4,5,3]
 * 返回值
 * [5,11,6,9,5]
 * 说明
 * 将所有元素变成  所需要施展魔法的最少次数为:
 *
 * [3-3] + [1-3] + [4-3] + [5-3] + [3-3] = 5
 *
 * 将所有元素变成  所需要施展魔法的最少次数为:
 *
 * [1-3] + [1-1] + [1-4] + [1-5] + [1-3] = 11
 *
 * 将所有元素变成  所需要施展魔法的最少次数为:
 *
 * [3-4] + [1-4] + [4-4] + [5-4] + [3-4] = 6
 *
 * 将所有元素变成  所需要施展魔法的最少次数为:
 *
 * [3-5] + [1-5] + [4-5] + [5-5] + [3-5] = 9
 *
 * 将所有元素变成  所需要施展魔法的最少次数为:
 *
 * [3-3] + [1-3] + [4-3] + [5-3] + [3-3] = 5
 *
 * 因此返回[5,11,6,9,5]
 *
 *  样例2
 * 输入
 * [1,2]
 * 返回值
 * [1,1]
 * 说明
 * 将所有元素变成所需要的次数为: 。
 * 将所有元素变成所需要的次数为: 。
 * 因此答案为[1,1]。
 * 备注:
 *
 * @author LIN
 * @date 2021-06-25
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param h int整型一维数组
     * @return int整型一维数组
     */
    public int[] Magical_NN (int[] h) {
        // write code here
        int size = h.length;
        int[][] tmp = new int[size][2];
        for(int i=0;i<size;i++){
            tmp[i][0] = h[i];
            tmp[i][1] = i;
        }
        Arrays.sort(tmp, Comparator.comparingInt(o -> o[0]));
        int[] s = new int[size];
        int sum = 0;
        for (int i=0;i< tmp.length;i++) {
            sum+=tmp[i][0];
            s[i] = sum;
        }
        for (int i = 0; i < size; i++) {
            if(i == 0){
                tmp[i][0] = s[size-1] - s[i] -(size-i-1)*tmp[i][0];
            }else{
                tmp[i][0] = s[size-1] - s[i] -(size-i-1)*tmp[i][0] + tmp[i][0] * (i) -s[i-1] ;
            }
            h[tmp[i][1]] = tmp[i][0];
        }
        return h;
    }

    public static void main(String[] args) {
        Solution solution = new Solution() {
        };
        int[] h = {3,1,4,5,3};
        solution.Magical_NN(h);
    }
}
